package me.mingshan.leetcode;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/palindrome-linked-list/
 * <p>
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 *
 * @author hanjuntao
 * @date 2025/8/6 0006
 */
public class L_234_回文链表 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(0);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(1);
        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
        System.out.println(isPalindrome2(node1));

    }

    /**
     * 判断是否是回文链表
     *
     * 1, 2,2, 1
     * mid = 3
     * 1, 2, 3, 2, 1
     * mid = 3
     *
     * 思路：
     *
     * 1. 找到中间节点
     * 2. 利用栈存储中间节点之前的节点
     * 3. 遍历中间节点之后的节点，与栈中的节点进行比较
     * 4. 如果所有节点都匹配，则返回 true，否则返回 false
     *
     *（时间复杂度：O(N), 空间复杂度：O(N)）
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode curr = head;
        int count = 0;
        while (curr != null) {
            count++;
            curr = curr.next;
        }

        int mid = count / 2 + 1;

        // 判断偶数
        boolean isEven = count % 2 == 0;

        Stack<Integer> stack = new Stack<>();

        count = 0;
        curr = head;
        while (curr != null) {
            count++;

            // 偶数
            if (isEven) {
                if (count >= mid) {
                    // 3 - 3 + 1
                    Integer lastI = stack.pop();
                    if (!lastI.equals(curr.val)) {
                        return false;
                    }
                } else {
                    stack.add(curr.val);
                }
            } else { // 奇数
                if (count > mid) {
                    // 3 - 3 + 1
                    Integer lastI = stack.pop();
                    if (!lastI.equals(curr.val)) {
                        return false;
                    }
                } else {
                    if (count != mid) {
                        stack.add(curr.val);
                    }
                }
            }

            curr = curr.next;
        }

        return true;
    }

    /**
     * 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
     *
     * 1. 找到中间节点
     * 2. 反转中间节点之后的节点
     * 3. 遍历中间节点之前的节点，与反转后的节点进行比较
     * 4. 如果所有节点都匹配，则返回 true，否则返回 false
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode curr = head;
        int count = 0;
        while (curr != null) {
            count++;
            curr = curr.next;
        }

        int mid = count / 2 + 1;

        // 判断偶数
        boolean isEven = count % 2 == 0;

        // 找到中间节点
        ListNode pre = null;
        curr = head;
        ListNode midHead = null;
        count = 0;
        while (curr != null) {
            count++;
            ListNode next = curr.next;

            if (isEven) {

                if (count == mid) {
                    // 从pre断开
                    pre.next = null;
                    midHead = curr;
                    break;
                }
            } else {
                if (count == mid) {
                    // 中间节点不要了
                    pre.next = null;
                    curr.next = null;
                    midHead = next;
                    break;
                }
            }

            pre = curr;
            curr = next;
        }

        if (midHead != null) {
            midHead = reverse(midHead);
        }

        // 遍历两个链表， 判断是否相等
        ListNode curr1 = head;
        ListNode curr2 = midHead;
        while (curr1 != null && curr2 != null) {
            if (curr1.val != curr2.val) {
                return false;
            }

            curr1 = curr1.next;
            curr2 = curr2.next;
        }

        return true;
    }

    private static ListNode reverse(ListNode midHead) {
        if (midHead == null || midHead.next == null) {
            return midHead;
        }

        ListNode newHead = reverse(midHead.next);

        // 当前节点的next 为后续新链表的尾节点
        // 将当前节点作为新的尾节点
        ListNode next = midHead.next;
        next.next = midHead;
        midHead.next = null;

        return newHead;
    }

}
